package com.lun.swordtowardoffer2.c04;

import com.lun.util.SinglyLinkedList.ListNode;

public class DetectCycle {
	
	//需要知道环中节点数目的解法
	public ListNode detectCycle(ListNode head) {
		ListNode inLoop = getNodeInLoop(head);
		
		if(inLoop == null) 
			return null;
		
		int loopCount = 1;
		for(ListNode n = inLoop; n.next != inLoop; n = n.next)
			loopCount++;
		
		ListNode first = head, second = head;
		
		while(loopCount-- > 0)
			first = first.next;
		
		
		while(first != second) {
			first = first.next;
			second = second.next;
		}
		
		return first;
	}
	
	//不需要知道环中节点数目的解法
	public ListNode detectCycle2(ListNode head) {
		ListNode inLoop = getNodeInLoop(head);
		
		if(inLoop == null) 
			return null;

		inLoop = inLoop.next;
		ListNode p = head;
		
		while(p != inLoop) {
			p = p.next;
			inLoop = inLoop.next;
		}
		
		return p;
	}
	
	private ListNode getNodeInLoop(ListNode head) {
		if(head == null || head.next == null)
			return null;
		
		ListNode slow = head;
		ListNode fast = slow.next;
				
		while(fast != null) {
			if(slow == fast) 
				break;
			
			slow = slow.next;
			fast = fast.next;
			if(fast != null)
				fast = fast.next;
		}
		
		return fast;
	}
	
}
